package Sort;

public class sort2 {
    //希尔排序
    public static void main(String[] args) {
        int[] arr = {10,5,21,6,7,2,9,11,3,1};
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
        shellSort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }

    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap>1){
            gap/=2;
            shell(arr,gap);
        }
    }
//这里是对插入排序进行修改
    private static void shell(int[] arr, int gap) {
        for (int i=gap;i<arr.length;i+=gap){
            int j=i-gap;

            int tmp = arr[i];
            while(j>=0){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                    j-=gap;
                }
                else{
                    break;
                }
            }
            arr[j+gap]=tmp;

        }
    }

}
